1. Field of the Invention
The present invention generally relates to general purpose digital scanning systems and more particularly relates to such systems that employ data compression as a means for reducing the file size of scanned images for data transmission and/or data storage.
2. Description of the Prior Art
Data compression is popular for reducing the amount of memory required to store digitized images. There are many types of documents which are typically stored as digitized images including engineering drawings, art work, and various other non-textual documents.
Scanners and video cameras can digitize documents thereby coding them as ones and zeros. Digitizing devices may view a document as a large number of pixels wherein each pixel represents a portion of the area of the document and each pixel has a degree of darkness. The degree of darkness of a particular pixel may fall on a light to dark continuum, which represents the grey scale of the pixel. One means of simplifying the process is to eliminate the grey scale wherein the digitizing device assigns a particular pixel a value of zero if the degree of darkness does not exceed a predetermined threshold of darkness (i.e. it is not very dark). Similarly, the digitizing device assigns the particular pixel a value of one if the degree of darkness does exceed the predetermined threshold of darkness. This simplification eliminates the grey scale and considers each pixel either black or white. In this way, a paper document may be represented as an array of pixels where each pixel may be represented by a one or a zero. A computer may be used to manipulate, store, or transmit the pixels as desired. The predetermined threshold of darkness can often be adjusted by the user of the digitizing device to best preserve the information in view of the loss of grey scale.
The number of bits or pixels in an image depends on the size of the image and on the resolution of the digitizing device. Resolution is a measure of the precision of the digitizing device and is typically expressed in Dots Per Inch (DPI). The greater the DPI of a digitizing device, the more likely the digitized image will appear similar to the original document when a computer displays or prints the digitized image. Common resolutions used today include 100, 150, 200, 240, and 300 DPI.
To illustrate the large amount of data that is generated when digitizing a document, the following example is set forth. At 200 DPI, which is not even at the high end of common resolutions that are used today, a digitized 8.5".times.11" sheet of paper requires about 3.7 megabits (i.e. 467,500 megabytes) of digitized data. The equivalent of four 1 megabit RAM's would be required to store this much data. In addition, approximately 6.5 minutes would be required to transmit this much data at rate of 9600 bits/second. It is clear that some sort of data reduction method had to be developed to efficiently handle these large data files.
In response thereto, designers have developed special encoding algorithms which have proved to substantially reduce the quantity of data while retaining all of the information contained therein. These algorithms have been termed data compression algorithms--or data compression. The amount of data after data compression divided by the amount of data before data compression is known as the compression ratio. A unique feature of "lossless" data compression algorithms is that a computer can decompress the compressed image and recover the original image. That is, no information is lost due to the compression step.
The field of data compression has many terms of art. A few of these terms will be defined and discussed. A "run" is a succession of pixels, all of which are one color. Runs alternate in color and stop at the end of a line. Run length refers to the number of successive pixels in a run. A busy image has a relatively short average run length whereas a non-busy image has a relatively long run length. Run-length coding-based compression algorithms are most effective on images that have relatively long average run lengths for reasons that will be discussed later. In fact, the average run length of an image has the greatest influence on compression efficiency and effectiveness.
Several commercial groups have attempted to negotiate standard compression algorithms to ensure compatibility between various manufacturer's products. One of these groups is the International Telegraph and Telephone Consultative Committee (CCITT). The CCITT is an international group representing many countries throughout the world. The CCITT has adopted several "standard" compression formats. Two of these standard formats, namely the Group-3 and the Group-4 standards formats, are now widely accepted throughout the world.
The CCITT standard compression formats can be classified into two general categories; 1-dimensional compression algorithms and 2-dimensional algorithms. Both the Group-3 and the Group-4 standard compression formats use either the 1-dimensional algorithms, the 2-dimensional algorithms or a combination thereof.
Group-3 1-dimensional encoding generally comprises a two step process. First, the run lengths of each run are calculated as discussed above. Second, the run lengths are substituted for codes. The codes are typically much shorter than the run length value themselves. The CCITT standards recognize that some run lengths are more likely to occur than other run lengths in a typical document. Researchers determined the probabilities of each run length occurring, which are not the same for white and black runs, and developed tables of codes to substitute for each run length value. The codes vary in size and the tables assign shorter codes to more likely run lengths. More importantly, the codes eliminate wasted bits because the codes are designed such that they may be spliced together without respecting byte boundaries. The Group-3 1-dimensional scheme may replace as many as 63 pixels with a single "terminating" code.
The Group-3 2-dimensional scheme produces a coding line with reference to a preceding reference line. That is, the transition points within the coding line are expressed relative to the transition points in an adjacent reference line. Two-dimensional compression schemes are very effective because in typical images, most coding lines differ very little from a corresponding reference line when the reference line is located adjacent thereto. Research has shown that 75% of transitions from one color to another color occur directly below or within one pixel to the left or right of a transition on the reference line. Two-dimensional schemes exploit this regularity by employing very short codes to express a run in terms of the transition points in the adjacent reference line. The Group-4 algorithm is an optimized version of the Group-3 algorithm.
Further information regarding the CCITT's standard compression formats can be found in Standardization of Group-3 Facsimile Apparatus For Document Transmission, CCITT, Recommendations T.4-T.6 (Geneva, 1980, amended at Malaga-Torremilinos, 1984), and Compression Algorithms Reduce Digitized Images to Manageable Size, William C. Warner, EDN, pp. 203-212, Jun. 21, 1990. These documents are expressly incorporated herein by reference.
The compression techniques described above are used widely today. Common uses include compressing executable files so that a software program may fit on a floppy disk, compressing data before it is transferred over a facsimile machine, or compressing backup files or other files that are not used regularly. Another popular use for data compression is for compressing digitized image files. There is a growing need to compress image files as digitizer and scanners become more cost effective and widely accepted.
One growing application where electronic image files are used extensively is that of electronically storing copies of paper documents. Often, an electronic copy of a document does not exist. An efficient way to create one is through image scanning and digitizing. Retaining electronic copies of documents, rather than keeping the paper documents themselves, can have significant advantages. First, electronic copies of digitized documents can be much more efficiently stored. Many documents can be placed on a single storage medium. Second, the electronic copies can be sent across existing telephone lines whereas the corresponding paper document have to be mailed or otherwise delivered. Finally, electronic copies can be used as a backup for paper copies of documents. That is, in the event that the paper copy is lost or destroyed, the electronic copy can be used in place thereof or visa-versa.
It has been recognized that the banking industry may benefit from such technology. In one specific application, the banking industry may use electronic scanning and digitizing for storing negotiable checks after they have been cashed. Typically, a clearing bank receives a check, makes a photographic copy thereof for backup purposes, and then transfers the original check back to the drawing bank via postage or other transfer means. Using electronic scanning and digitizing technology, the clearing bank may electronically digitize the paper check received and then either: (1) transfer only the electronically digitized information back to the drawing bank; or (2) transfer the paper check and use the electronically digitized copy of the check for backup purposes. Potential advantages of transferring only the electronically digitized information to the drawing bank may include saving on postage costs and increasing the speed at which the check is transferred to the drawing bank. A potential advantage of using the electronically digitized copy of the check as a backup includes saving on photocopy and storage costs. The aforementioned applications of electronically digitizing technology are only exemplary and it is recognized that other advantages may be realized in the banking industry. Further, it is recognized that numerous other applications exist in other industries as well.
A particular problem that may arise when documents are to be routinely digitized is that some documents may require more memory to store the resulting image than other documents. For example, a "busy" document may require more memory to store than a corresponding "clean" document, even after data compression. As previously stated, busy documents may have a relatively short average run length while clean documents may have a relatively long average run length. Taken to the extreme, a document that results in a "checkerboard" pattern after digitization is the busiest document that can be realized because the average run length will equal one. Conversely, a document that results in an all white pattern after digitization is the cleanest document that can be realized because the average run length will equal the line length.
It has been estimated that a maximum sized standard check having a checkerboard pattern may require approximately 1.28 MB of memory after compression. A same sized check having an all white pattern may require approximately 4 KB of memory. Therefore, if enough memory is provided to store the worst case image, a substantial amount of memory may be wasted when "average" documents are digitized and stored.
It is thus recognized that when a system has the capability to routinely digitize and store various images, the system designer must either provide enough memory to store the worst case image or sacrifice a portion of the worst case image in the interests of system efficiency. That is, when only a portion of the memory that is required to store the worst case image is provided in the system, a portion of a worst case image must be truncated at some point. The truncation point will be dictated by the amount of memory provided in the system.
Several methods may be used to compensate for the limitation of memory including: (1) aggressively increasing the threshold of what is considered a "1" by the digitizing device thereby decreasing the number of ones within the image and thus making the worst case "checkerboard pattern" much less likely to occur; or (2) simply stopping the stream of compressed data once a predetermined memory limitation has been exceeded. A disadvantage of the first method above is that the image may be washed out to the point of illegibility. A disadvantage of the second method above is that a decompressor may detect an error when decompressing the image because the image data will most probably be abruptly interrupted in the middle of a row. Another disadvantage of the second method is that the number of rows which were actually compressed by the compressor will be unknown. The primary disadvantage is that the number of pixels actually stored will vary as between documents of the same size, thus not preserving the size of the document stored.